package dp.贪心;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 跳跃游戏55.java
 * @Description https://leetcode-cn.com/problems/jump-game-ii/
 * @createTime 2021年12月20日 20:47:00
 */
public class 跳跃游戏II45 {
	public int jump(int[] nums) {
		//终点
		int length = nums.length;
		//上次跳跃的最右边
		int end = 0;
		//步数
		int step = 0;
		//目前能跳跃的最大位置
		int max = 0;

		for (int i = 0; i < length - 1; i++) {
			//当前步数能到的最大位置
			max = Math.max(max, i + nums[i]);
			//如果到达了上次跳跃的边界
			if (end == i) {
				end=max;
				step++;
			}
		}
		return step;
	}
}
